
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <title>12 算法 · C++导览 第二版 简体中文版</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="HonKit 5.1.1">
        <meta name="author" content="Windsting">
        
        
    
    <link rel="stylesheet" href="gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="gitbook/@dogatana/honkit-plugin-page-toc-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/@dogatana/honkit-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-forkmegithub/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/@honkit/honkit-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-search/search.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
        <link rel="stylesheet" href="styles/website.css">
        
    
        
    
        
    
        
    
        
    
        
    

        
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="ch13.html" />
    
    
    <link rel="prev" href="ch11.html" />
    

    </head>
    <body>
        
<div class="book honkit-cloak">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    
    
        
        <li>
            <a href="https://github.com/windsting/a-tour-of-cpp-2nd-cn" target="_blank" class="custom-link">Github Link</a>
        </li>
    
    

    
    <li class="divider"></li>
    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="translation_note.html">
            
                <a href="translation_note.html">
            
                    
                    译者言
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="./">
            
                <a href="./">
            
                    
                    前言
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="ch01.html">
            
                <a href="ch01.html">
            
                    
                    1 基础知识
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="ch02.html">
            
                <a href="ch02.html">
            
                    
                    2 用户定义类型
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="ch03.html">
            
                <a href="ch03.html">
            
                    
                    3 模块化
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="ch04.html">
            
                <a href="ch04.html">
            
                    
                    4 类
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="ch05.html">
            
                <a href="ch05.html">
            
                    
                    5 基本操作
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="ch06.html">
            
                <a href="ch06.html">
            
                    
                    6 模板
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="ch07.html">
            
                <a href="ch07.html">
            
                    
                    7 概束和泛型编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.10" data-path="ch08.html">
            
                <a href="ch08.html">
            
                    
                    8 标准库概览
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.11" data-path="ch09.html">
            
                <a href="ch09.html">
            
                    
                    9 字符串和正则表达式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.12" data-path="ch10.html">
            
                <a href="ch10.html">
            
                    
                    10 输入输出
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.13" data-path="ch11.html">
            
                <a href="ch11.html">
            
                    
                    11 容器
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.14" data-path="ch12.html">
            
                <a href="ch12.html">
            
                    
                    12 算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.15" data-path="ch13.html">
            
                <a href="ch13.html">
            
                    
                    13 实用功能
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.16" data-path="ch14.html">
            
                <a href="ch14.html">
            
                    
                    14 数值
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.17" data-path="ch15.html">
            
                <a href="ch15.html">
            
                    
                    15 并发
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.18" data-path="ch16.html">
            
                <a href="ch16.html">
            
                    
                    16 历史及兼容性
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.19" data-path="idx.html">
            
                <a href="idx.html">
            
                    
                    索引
            
                </a>
            

            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://github.com/honkit/honkit" target="blank" class="gitbook-link">
            本书使用 HonKit 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="." >12 算法</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                

    
        
                                <p><a class="en-page-number" id="149"></a></p>
<div class="chapter-number"><p class="chapter-number">12</p></div>

<h1 id="algorithm">算法 </h1>
<blockquote>
<p>若无必要，勿增实体。</p>
<p><span title="著名的“奥卡姆剃刀”法则，此处作者可能误会了说这短引言作者的名字，因为其名字应该是“William of Occam”，意思是“奥卡姆这个地方的威廉”，作者的写法里“奥卡姆”是他的姓。该名词的维基百科页面为： https://zh.wikipedia.org/wiki/%E5%A5%A5%E5%8D%A1%E5%A7%86%E5%89%83%E5%88%80">—— 威廉·奥卡姆</span><sup><a href="#fn_1" id="reffn_1">1</a></sup></p>
</blockquote>
<h2 id="12.1">12.1 导言 </h2>
<p>如果单打独斗，<code>vector</code>和<code>list</code>这些数据结构的用途颇为有限。
使用时，我们需要添加和删除元素这些基本操作（就像<code>list</code>和<code>vector</code>实现的那样）。
不过，使用容器仅仅存储对象的情况寥寥无几。
而是还要排序、打印、提取子集、移除元素、查找对象等等。
相应地，标准库里除了最常见的容器类型之外，还为这些容器提供了最常见的算法。
例如，我们可以简单高效地把持有<code>Entry</code>的<code>vector</code>进行排序，
并为<code>vector</code>中每个不重复的元素在<code>list</code>中创建副本：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">f</span><span class="hljs-params">(vector&lt;Entry&gt;&amp; vec, list&lt;Entry&gt;&amp; lst)</span>
</span>{
    <span class="hljs-built_in">sort</span>(vec.<span class="hljs-built_in">begin</span>(),vec.<span class="hljs-built_in">end</span>());                    <span class="hljs-comment">// 用 &lt; 进行排序</span>
    <span class="hljs-built_in">unique_copy</span>(vec.<span class="hljs-built_in">begin</span>(),vec.<span class="hljs-built_in">end</span>(),lst.<span class="hljs-built_in">begin</span>()); <span class="hljs-comment">// 不复制相邻的等值元素</span>
}
</code></pre>
<p><a class="en-page-number" id="150"></a></p>
<p>要让这段代码运行，必须为<code>Entry</code>定义小于（<code>&lt;</code>）和等于（<code>==</code>）操作。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-type">bool</span> <span class="hljs-keyword">operator</span>&lt;(<span class="hljs-type">const</span> Entry&amp; x, <span class="hljs-type">const</span> Entry&amp; y) <span class="hljs-comment">// 小于</span>
{
    <span class="hljs-keyword">return</span> x.name&lt;y.name;           <span class="hljs-comment">// 用 name 给 Entry 排序</span>
}
</code></pre>
<p>标准算法以元素的（半开）序列的方式表示。
一个<em>序列（sequence）</em>以指向首元素和尾元素后位置的一对迭代器表示：</p>
<p><img src="img/ch12_01.png" alt="sequence"></p>
<p>在本例中，<code>sort()</code>为<code>vec.begin()</code>和<code>vec.end()</code>
定义的 迭代器对 定义的序列排序，该 迭代器对 恰好包括了<code>vector</code>的全部元素。
对于写（输出）操作，仅需指定待写入的首元素位置。
如果有不止一个元素输出，起始元素后的元素会被覆盖。
就是说，要避免出错，<code>lst</code>的元素数量至少跟<code>vec</code>中不重复值的数量一样多。</p>
<p>如果要把不重复元素放进一个新（空的）容器里，应该这么写：</p>
<pre><code class="lang-cpp"><span class="hljs-function">list&lt;Entry&gt; <span class="hljs-title">f</span><span class="hljs-params">(vector&lt;Entry&gt;&amp; vec)</span>
</span>{
    list&lt;Entry&gt; res;
    <span class="hljs-built_in">sort</span>(vec.<span class="hljs-built_in">begin</span>(),vec.<span class="hljs-built_in">end</span>());
    <span class="hljs-built_in">unique_copy</span>(vec.<span class="hljs-built_in">begin</span>(),vec.<span class="hljs-built_in">end</span>(),<span class="hljs-built_in">back_inserter</span>(res));  <span class="hljs-comment">// 添加到 res 尾部</span>
    <span class="hljs-keyword">return</span> res;
}
</code></pre>
<p><code>back_inserter(res)</code>这个调用为<code>res</code>在容器末尾构造一个迭代器，
并且用它添加这些元素，为它们扩展容器以便提供存储空间。
这样我们就盛事了，不必去先分配一块固定容量的空间，而后再填充它。
于是，标准容器加上<code>back_inserter()</code>消灭了对<code>realloc()</code>
——这个易出错的显式C-风格内存管理——的需求。
标准库容器<code>list</code>有个转移构造函数（§5.2.2），
它可以令<code>res</code>的传值返回变得高效（哪怕是装载着成千上万元素的<code>list</code>）。</p>
<p>如果你觉得这个 迭代器对 风格的代码
——例如<code>sort(vec.begin(),vec.end())</code>——繁琐，
还可以定义容器版本的算法，然后这么写<code>sort(vec)</code>（§12.8）。</p>
<h2 id="12.2">12.2 迭代器应用 </h2>
<p>对于某个容器，有几个指向特定元素的迭代器可以获取；
<code>begin()</code>和<code>end()</code>就是这种例子。
另外，很多算法也会返回迭代器。
例如，标准算法<code>find()</code>在某个序列中查找一个值并返回指向该元素的迭代器：</p>
<p><a class="en-page-number" id="151"></a></p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">bool</span> <span class="hljs-title">has_c</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s, <span class="hljs-type">char</span> c)</span>     <span class="hljs-comment">// s 是否包含字符 c ？</span>
</span>{
    <span class="hljs-keyword">auto</span> p = <span class="hljs-built_in">find</span>(s.<span class="hljs-built_in">begin</span>(),s.<span class="hljs-built_in">end</span>(),c);
    <span class="hljs-keyword">if</span> (p!=s.<span class="hljs-built_in">end</span>())
        <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
    <span class="hljs-keyword">else</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
}
</code></pre>
<p>与很多标准库查找算法相似，<code>find()</code>返回<code>end()</code>以表示“未找到（not found）”。
一个等价且更简短的<code>has_c()</code>定义是：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">bool</span> <span class="hljs-title">has_c</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s, <span class="hljs-type">char</span> c)</span>     <span class="hljs-comment">// s 是否包含字符 c ？</span>
</span>{
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">find</span>(s.<span class="hljs-built_in">begin</span>(),s.<span class="hljs-built_in">end</span>(),c)!=s.<span class="hljs-built_in">end</span>();
}
</code></pre>
<p>一个更有意思的练习是找到一个字符在某字符串中出现的所有位置。
我们可以返回以承载 <code>string</code>迭代器 的<code>vector</code>，以表示的出现位置集合。
返回<code>vector</code>是高效的，因为它提供了转移语意（§5.2.1）。
如果我们想对找到的位置进行修改，就需要传入 非-<code>const</code> 字符串：</p>
<pre><code class="lang-cpp"><span class="hljs-function">vector&lt;string::iterator&gt; <span class="hljs-title">find_all</span><span class="hljs-params">(string&amp; s, <span class="hljs-type">char</span> c)</span>    <span class="hljs-comment">// 查找s中出现的所有c</span>
</span>{
    vector&lt;string::iterator&gt; res;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p = s.<span class="hljs-built_in">begin</span>(); p!=s.<span class="hljs-built_in">end</span>(); ++p)
        <span class="hljs-keyword">if</span> (*p==c)
            res.<span class="hljs-built_in">push_back</span>(p);
    <span class="hljs-keyword">return</span> res;
}
</code></pre>
<p>我们用一个常规的循环在这个字符串中进行遍历，
借助<code>++</code>每次把迭代器<code>p</code>向容器尾部移动一个元素，
并借助解引用操作符<code>*</code>查看这些元素。可以这样测试<code>find_all()</code>：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">test</span><span class="hljs-params">()</span> </span>{
    string m {<span class="hljs-string">&quot;Mary had a little lamb&quot;</span>};
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p : <span class="hljs-built_in">find_all</span>(m,<span class="hljs-string">&apos;a&apos;</span>))
        <span class="hljs-keyword">if</span> (*p!=<span class="hljs-string">&apos;a&apos;</span>)
            cerr &lt;&lt; <span class="hljs-string">&quot;a bug!\n&quot;</span>;
}
</code></pre>
<p>上面的<code>find_all()</code>调用可图示如下：</p>
<p><img src="img/ch12_02.png" alt="find_all"></p>
<p><a class="en-page-number" id="152"></a></p>
<p>对于每个合乎情理的使用情形而言，迭代器和标准算法在所有标准容器上的应用都是等效的。
因此，可以这样泛化<code>find_all()</code>：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> C, <span class="hljs-keyword">typename</span> V&gt;
vector&lt;<span class="hljs-keyword">typename</span> C::iterator&gt; <span class="hljs-title">find_all</span><span class="hljs-params">(C&amp; c, V v)</span> </span>{  <span class="hljs-comment">// 查找v中出现的所有c</span>
    vector&lt;<span class="hljs-keyword">typename</span> C::iterator&gt; res;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p = c.<span class="hljs-built_in">begin</span>(); p!=c.<span class="hljs-built_in">end</span>(); ++p)
        <span class="hljs-keyword">if</span> (*p==v)
            res.<span class="hljs-built_in">push_back</span>(p);
    <span class="hljs-keyword">return</span> res;
}
</code></pre>
<p>为了让编译器知道<code>C</code>的<code>iterator</code>应该被推断为类型而非一个值，比方说整数<code>7</code>，
那个<code>typename</code>是必须的。
可以为<code>iterator</code>引入一个类型别名（§6.4.2）以隐藏这个实现细节：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-keyword">using</span> Iterator = <span class="hljs-keyword">typename</span> T::iterator;          <span class="hljs-comment">// T的迭代器</span>

<span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> C, <span class="hljs-keyword">typename</span> V&gt;
vector&lt;Iterator&lt;C&gt;&gt; <span class="hljs-built_in">find_all</span>(C&amp; c, V v)         <span class="hljs-comment">// 查找v中出现的所有c</span>
{
    vector&lt;Iterator&lt;C&gt;&gt; res;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p = c.<span class="hljs-built_in">begin</span>(); p!=c.<span class="hljs-built_in">end</span>(); ++p)
        <span class="hljs-keyword">if</span> (*p==v)
            res.<span class="hljs-built_in">push_back</span>(p);
    <span class="hljs-keyword">return</span> res;
}
</code></pre>
<p>现在可以这样写：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">test</span><span class="hljs-params">()</span>
</span>{
    string m {<span class="hljs-string">&quot;Mary had a little lamb&quot;</span>};

    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p : <span class="hljs-built_in">find_all</span>(m,<span class="hljs-string">&apos;a&apos;</span>))      <span class="hljs-comment">// p是个 string::iterator</span>
        <span class="hljs-keyword">if</span> (*p!=<span class="hljs-string">&apos;a&apos;</span>)
            cerr &lt;&lt; <span class="hljs-string">&quot;string bug!\n&quot;</span>;

    list&lt;<span class="hljs-type">double</span>&gt; ld {<span class="hljs-number">1.1</span>, <span class="hljs-number">2.2</span>, <span class="hljs-number">3.3</span>, <span class="hljs-number">1.1</span>};
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p : <span class="hljs-built_in">find_all</span>(ld,<span class="hljs-number">1.1</span>))     <span class="hljs-comment">// p是个 list&lt;double&gt;::iterator</span>
        <span class="hljs-keyword">if</span> (*p!=<span class="hljs-number">1.1</span>)
            cerr &lt;&lt; <span class="hljs-string">&quot;list bug!\n&quot;</span>;

    vector&lt;string&gt; vs { <span class="hljs-string">&quot;red&quot;</span>, <span class="hljs-string">&quot;blue&quot;</span>, <span class="hljs-string">&quot;green&quot;</span>, <span class="hljs-string">&quot;green&quot;</span>, <span class="hljs-string">&quot;orange&quot;</span>, <span class="hljs-string">&quot;green&quot;</span> }; 
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p : <span class="hljs-built_in">find_all</span>(vs,<span class="hljs-string">&quot;red&quot;</span>))   <span class="hljs-comment">// p是个 vector&lt;string&gt;::iterator</span>
        <span class="hljs-keyword">if</span> (*p!=<span class="hljs-string">&quot;red&quot;</span>)
            cerr &lt;&lt; <span class="hljs-string">&quot;vector bug!\n&quot;</span>;
</code></pre>
<p><a class="en-page-number" id="153"></a></p>
<pre><code class="lang-cpp">    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p : <span class="hljs-built_in">find_all</span>(vs,<span class="hljs-string">&quot;green&quot;</span>))
        *p = <span class="hljs-string">&quot;vert&quot;</span>;
}
</code></pre>
<p>迭代器的作用是分离算法和容器。
算法通过迭代器操作数据，并对元素所在的容器一无所知。
反之，容器对操作元素的算法也是不知所以；
它所做的不过是按需提供迭代器（即<code>begin()</code>和<code>end()</code>）而已。
这种把数据存储和算法分离的模型催生出了泛化且灵活的软件。</p>
<h2 id="12.3">12.3 迭代器类型 </h2>
<p>到底什么是迭代器？任何迭代器都是某种类型的一个对象。
只不过，有着很多种不同的迭代器类型，
因为一个迭代器需要为特定的容器类型保存作业所需的信息。
这些迭代器类型可以像容器那般多种多样，还可以按实际情况进行特化。
例如，<code>vector</code>的迭代器可以是普通的指针，
因为需要指向<code>vector</code>元素的时候，指针是个相当合理的的方式：</p>
<p><img src="img/ch12_03.png" alt="vector-iterator-pointer"></p>
<p>或者，<code>vector</code>迭代器也可以实现为指向<code>vector</code>的指针外加一个索引：</p>
<p><img src="img/ch12_04.png" alt="vector-iterator-pointer-plus-index"></p>
<p>使用这种迭代器可以进行越界检查。</p>
<p><code>list</code>迭代器不得不比指向元素的指针更复杂一些，
因为一般来说<code>list</code>的元素并不知道该<code>list</code>中下一个元素在哪儿。
因此，<code>list</code>的迭代器有可能是个指向节点的指针：</p>
<p><img src="img/ch12_05.png" alt="list-iterator"></p>
<p>所有迭代器共通的部分是它们的语意和操作的命名。
例如，对任何迭代器应用<code>++</code>都会得到指向指向下一个元素的迭代器。
类似地，用<code>*</code>可以得到该迭代器指向的元素。</p>
<p><a class="en-page-number" id="154"></a></p>
<p>实际上，任何对象，只要符合几个诸如此类的简单规则就是一个迭代器
——<em>迭代器（Iterator）</em>是个概束（§7.2，§12.7）。
另外，用户极少需要知道具体迭代器的类型；每个容器都“知道”它自己迭代器类型，
并按惯例以<code>iterator</code>和<code>const_iterator</code>为名称提供它们。
例如，<code>list&lt;Entry&gt;::iterator</code>就是<code>list&lt;Entry&gt;</code>的通用迭代器类型。
我们几乎没必要操心该类型定义的细节。</p>
<h2 id="12.4">12.4 流迭代器 </h2>
<p>在处理容器中的元素序列时，迭代器是个通用且便利的概念。
但是，容器并非元素序列栖身的唯一所在。
例如，一个输入流产生一个值序列，另外，我们会向输出流写入值序列。
所以，迭代器的概念在输入和输出方面的应用也颇为有益。</p>
<p>要得到一个<code>ostream_iterator</code>，需要指定使用的流以及待写入对象的类型。
例如：</p>
<pre><code class="lang-cpp">ostream_iterator&lt;string&gt; oo {cout}; <span class="hljs-comment">// 向cout写入string</span>
</code></pre>
<p>给<code>*oo</code>赋值待结果就是把该值写入到<code>cout</code>。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    *oo = <span class="hljs-string">&quot;Hello, &quot;</span>;    <span class="hljs-comment">// 意思是cout&lt;&lt;&quot;Hello, &quot;</span>
    ++oo;
    *oo = <span class="hljs-string">&quot;world!\n&quot;</span>;   <span class="hljs-comment">// 意思是cout&lt;&lt;&quot;world!\n&quot;</span>
}
</code></pre>
<p>这是另一种将规范化消息写向标准输出的方式。
<code>++oo</code>模拟了利用指针向数组写入的行为。</p>
<p>类似地，<code>istream_iterator</code>允许我们把一个输入流作为只读容器使用。
同样，还是要指定使用的流和待读取对象的类型：</p>
<pre><code class="lang-cpp">istream_iterator&lt;string&gt; ii {cin};
</code></pre>
<p>输入迭代器通常成对出现来表示一个序列，
因此还需要提供一个<code>istream_iterator</code>以表示输入的末尾。
这就是默认的<code>istream_iterator</code>：</p>
<pre><code class="lang-cpp">istream_iterator&lt;string&gt; eos {};
</code></pre>
<p>一般来说，<code>istream_iterator</code>和<code>ostream_iterator</code>不会直接拿来就用。
而是会作为参数传递给算法去使用。
例如，可以写个简单的程序读取文件，把读到的单词排序、去重，
然后把结果写入到另一个文件：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    string from, to;
    cin &gt;&gt; from &gt;&gt; to;                      <span class="hljs-comment">// 获取源文件名和目标文件名</span>

    ifstream is {from};                     <span class="hljs-comment">// 以&quot;from&quot;文件作为输入流</span>
    istream_iterator&lt;string&gt; ii {is};       <span class="hljs-comment">// 流的输入迭代器</span>
    istream_iterator&lt;string&gt; eos {};        <span class="hljs-comment">// 输入截止信号</span>
</code></pre>
<p><a class="en-page-number" id="155"></a></p>
<pre><code class="lang-cpp">    ofstream os {to};                       <span class="hljs-comment">// 以&quot;to&quot;文件作为输出流</span>
    ostream_iterator&lt;string&gt; oo {os,<span class="hljs-string">&quot;\n&quot;</span>};  <span class="hljs-comment">// 流的输出迭代器</span>

    vector&lt;string&gt; b {ii,eos};              <span class="hljs-comment">// b 是个以输入流初始化的vector</span>
    <span class="hljs-built_in">sort</span>(b.<span class="hljs-built_in">begin</span>(),b.<span class="hljs-built_in">end</span>());                <span class="hljs-comment">// 给缓存排序</span>

    <span class="hljs-built_in">unique_copy</span>(b.<span class="hljs-built_in">begin</span>(),b.<span class="hljs-built_in">end</span>(),oo);      <span class="hljs-comment">// 把缓存复制到输出流，丢弃重复的值</span>

    <span class="hljs-keyword">return</span> !is.<span class="hljs-built_in">eof</span>() || !os;                <span class="hljs-comment">// 返回错误状态（§1.2.1， §10.4）</span>
}
</code></pre>
<p><code>ifstream</code>是个可附着到文件上的<code>istream</code>，
而一个<code>ofstream</code>是个可以附着到文件的<code>ostream</code>（§10.7）。
<code>ostream_iterator</code>的第二个参数用于分隔输出值。</p>
<p>实际上，此程序没必要写这么长。
我们将字符串读取到<code>vector</code>，然后给它们<code>sort()</code>,继而去重再输出。
更优雅的方案是根本不存储重复值。
要做到这一点，可以把<code>string</code>存储在<code>set</code>中，
<code>set</code>不会保存重复的值，并且会维持元素的顺序（§11.4）。
这样，可以把使用<code>vector</code>的两行代码以使用<code>set</code>的一行取代，
并使用更简单的<code>copy()</code>取代<code>unique_copy()</code>：</p>
<pre><code class="lang-cpp">set&lt;string&gt; b {ii,eos};         <span class="hljs-comment">// 从输入流收集字符串</span>
<span class="hljs-built_in">copy</span>(b.<span class="hljs-built_in">begin</span>(),b.<span class="hljs-built_in">end</span>(),oo);     <span class="hljs-comment">// 把缓存复制到输出流</span>
</code></pre>
<p><code>ii</code>、<code>eos</code>和<code>oo</code>都只用了一次，因此可以进一步缩减程序的代码量：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    string from, to;
    cin &gt;&gt; from &gt;&gt; to;      <span class="hljs-comment">// 获取源文件名和目标文件名</span>

    ifstream is {from};     <span class="hljs-comment">// 以&quot;from&quot;文件作为输入流</span>
    ofstream os {to};       <span class="hljs-comment">// 以&quot;to&quot;文件作为输出流</span>

    set&lt;string&gt; b {istream_iterator&lt;string&gt;{is},istream_iterator&lt;string&gt;{}};    <span class="hljs-comment">// 读输入流</span>
    <span class="hljs-built_in">copy</span>(b.<span class="hljs-built_in">begin</span>(),b.<span class="hljs-built_in">end</span>(),ostream_iterator&lt;string&gt;{os,<span class="hljs-string">&quot;\n&quot;</span>});                  <span class="hljs-comment">// 复制到输出流</span>

    <span class="hljs-keyword">return</span> !is.<span class="hljs-built_in">eof</span>() || !os;    <span class="hljs-comment">// 返回错误状态（§1.2.1， §10.4）</span>
}
</code></pre>
<p>至于最后一步简化是否提高可读性，取决于个人偏好和经验。</p>
<h2 id="12.5">12.5 谓词 </h2>
<p>到目前为止，例子中的算法对序列中的元素执行简单的“内建（built in）”操作。
但是，我们经常需要把这个操作作为参数传给算法。
比方说，算法<code>find</code>（§12.2，§12.6）提供了便捷的方式查找特定的值。
有个更通用的变体可以查找一个符合特定条件——<em>谓词（predicate）</em>——的元素。
例如，我们可能需要在一个<code>map</code>里查找第一个大于<code>42</code>的值。
<code>map</code>对其元素以<em>(key,value)</em>对的序列的方式提供访问，
因此，可以在<code>map&lt;string,int&gt;</code>查找一个其<code>int</code>大于<code>42</code>的<code>pair&lt;const string,int&gt;</code>：</p>
<p><a class="en-page-number" id="156"></a></p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">f</span><span class="hljs-params">(map&lt;string,<span class="hljs-type">int</span>&gt;&amp; m)</span>
</span>{
    <span class="hljs-keyword">auto</span> p = <span class="hljs-built_in">find_if</span>(m.<span class="hljs-built_in">begin</span>(),m.<span class="hljs-built_in">end</span>(),Greater_than{<span class="hljs-number">42</span>});
    <span class="hljs-comment">// ...</span>
}
</code></pre>
<p>此处，<code>Greater_than</code>是个函数对象（§6.3.2）持有<code>42</code>以便用于比对操作：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">struct</span> <span class="hljs-title class_">Greater_than</span> {
    <span class="hljs-type">int</span> val;
    <span class="hljs-built_in">Greater_than</span>(<span class="hljs-type">int</span> v) : val{v} { }
    <span class="hljs-function"><span class="hljs-type">bool</span> <span class="hljs-title">operator</span><span class="hljs-params">()</span><span class="hljs-params">(<span class="hljs-type">const</span> <span class="hljs-keyword">auto</span>&amp; r)</span> <span class="hljs-type">const</span> </span>{ <span class="hljs-keyword">return</span> r.second&gt;val; }
};
</code></pre>
<p>此外，还可以使用lambda表达式（§6.3.2）：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">auto</span> p = <span class="hljs-built_in">find_if</span>(m.<span class="hljs-built_in">begin</span>(), m.<span class="hljs-built_in">end</span>(), [](<span class="hljs-type">const</span> <span class="hljs-keyword">auto</span>&amp; r) { <span class="hljs-keyword">return</span> r.second&gt;<span class="hljs-number">42</span>; });
</code></pre>
<p>谓词不能对其访问的元素进行修改。</p>
<h2 id="12.6">12.6 算法概览 </h2>
<p>算法的通用定义是
“由规则组成的有限集合，这些规则为解决一组特定问题规定一系列操作，（并）具有五个重要特性：
有限性……确定性……输入……输出……高效性” [Knuth,1968,§1.1]。
在C++标准库的语境里，算法是一个对元素序列执行操作的函数模板。</p>
<p>标准库提供了数十种算法。这些算法定义在命名空间<code>std</code>中，
呈现在<code>&lt;algorithm&gt;</code>头文件里。
这些标准库算法全都以序列作为输入。
一个从<code>b</code>到<code>e</code>的半开区间序列表示为[<code>b</code>:<code>e</code>)。
以下是几个范例：</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>部分标准库算法 &lt;algorithm&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>f=for_each(b,e,f)</code></td>
            <td>为[<code>b</code>:<code>e</code>)中的每个元素执行<code>f(x)</code></td>
        </tr>
        <tr>
            <td><code>p=find(b,e,x)</code></td>
            <td><code>p</code>是[<code>b</code>:<code>e</code>)中第一个满足<code>*p==x</code>的<code>p</code></td>
        </tr>
        <tr>
            <td><code>p=find_if(b,e,f)</code></td>
            <td><code>p</code>是[<code>b</code>:<code>e</code>)中第一个满足<code>f(*p)</code>的<code>p</code></td>
        </tr>
        <tr>
            <td><code>n=count(b,e,x)</code></td>
            <td><code>n</code>是[<code>b</code>:<code>e</code>)中满足<code>*q==x</code>的元素<code>*q</code>的数量</td>
        </tr>
        <tr>
            <td><code>n=count_if(b,e,f)</code></td>
            <td><code>n</code>是[<code>b</code>:<code>e</code>)中满足<code>f(*q)</code>的元素<code>*q</code>的数量</td>
        </tr>
        <tr>
            <td><code>replace(b,e,v,v2)</code></td>
            <td>在[<code>b</code>:<code>e</code>)中用<code>v2</code>替换满足<code>*q==v</code>的元素<code>*q</code></td>
        </tr>
        <tr>
            <td><code>replace_if(b,e,f,v2)</code></td>
            <td>在[<code>b</code>:<code>e</code>)中用<code>v2</code>替换满足<code>f(*q)</code>的元素<code>*q</code></td>
        </tr>
        <tr>
            <td><code>p=copy(b,e,out)</code></td>
            <td>从[<code>b</code>:<code>e</code>)复制到[<code>out</code>:<code>p</code>)</td>
        </tr>
        <tr>
            <td><code>p=copy_if(b,e,out,f)</code></td>
            <td>从[<code>b</code>:<code>e</code>)复制满足<code>f(*q)</code>的元素<code>*q</code>到[<code>out</code>:<code>p</code>)</td>
        </tr>
        <tr>
            <td><code>p=move(b,e,out)</code></td>
            <td>从[<code>b</code>:<code>e</code>)移动到[<code>out</code>:<code>p</code>)</td>
        </tr>
        <tr>
            <td><code>p=unique_copy(b,e,out)</code></td>
            <td>从[<code>b</code>:<code>e</code>)复制到[<code>out</code>:<code>p</code>)；相邻的重复元素不复制</td>
        </tr>
        <tr>
            <td><code>sort(b,e)</code></td>
            <td>以<code>&lt;</code>作为排序依据，对[<code>b</code>:<code>e</code>)中的元素进行排序</td>
        </tr>
        <tr>
            <td><code>sort(b,e,f)</code></td>
            <td>以<code>f</code>作为排序依据，对[<code>b</code>:<code>e</code>)中的元素进行排序</td>
        </tr>
        <tr>
            <td><code>(p1,p2)=equal_range(b,e,v)</code></td>
            <td>[<code>p1</code>:<code>p2</code>)是有序序列[<code>b</code>:<code>e</code>)中值为<code>v</code>的子序列；大体上就是针对<code>v</code>的二分查找</td>
        </tr>
    </tbody>
</table>

<p><a class="en-page-number" id="157"></a></p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>部分标准库算法 &lt;algorithm&gt;（续表）</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>p=merge(b,e,b2,e2,out)</code></td>
            <td>把[<code>b</code>:<code>e</code>)和[<code>b2</code>:<code>e2</code>)两个有序序列和并进[<code>out</code>:<code>p</code>)</td>
        </tr>
        <tr>
            <td><code>p=merge(b,e,b2,e2,out,f)</code></td>
            <td>把[<code>b</code>:<code>e</code>)和[<code>b2</code>:<code>e2</code>)两个有序序列和并进[<code>out</code>:<code>p</code>)，以<code>f</code>作为比对依据</td>
        </tr>
    </tbody>
</table>

<p>此处和许多其它的算法（见 §14.3），可应用于容器、<code>string</code>以及内建数组的元素。</p>
<p>有些算法，例如<code>replace()</code>和<code>sort()</code>，修改元素值，
但不存在将容器元素增加或减少的算法。
原因是，一个序列并不知道持有此元素序列的是什么容器。
要增加或删除元素，你需要某个了解该容器的事物（比方 <code>back_inserter</code>；§12.1）
或者直接在容器上进行操作（即 <code>push_back()</code>或<code>erase()</code>；§11.2）。</p>
<p>Lambda表达式经常作为操作以参数的形式传递，例如：</p>
<pre><code class="lang-cpp">vector&lt;<span class="hljs-type">int</span>&gt; v = {<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>};
for_each(v.<span class="hljs-built_in">begin</span>(),v.<span class="hljs-built_in">end</span>(),[](<span class="hljs-type">int</span>&amp; x){ x=x*x; }); <span class="hljs-comment">// v=={0,1,4,9,16,25}</span>
</code></pre>
<p>相较于手工书写的循环，标准库算法通常更谨慎、更有针对性地进行设计和实现，
因此，请了解并使用它们，以避免重复造轮子。</p>
<h2 id="12.7">12.7 概束 </h2>
<p>在C++20中，标准库算法会被指定概束（第7章）。
相关的初期准备工作请参考 Ranges Technical Specification[RangesTS]。
其具体实现可以在互联网上找到。
对于C++20，区间这个概束定义在<code>&lt;ranges&gt;</code>中。</p>
<p><code>Range</code>是针对 通过<code>begin()</code>/<code>end()</code>定义的C++98序列 的一个泛化。
<code>Range</code>是个指定元素序列概念的概束。它的定义包括：</p>
<ul>
<li>一个迭代器的<code>{begin,end}</code>对</li>
<li>一个<code>{begin,n}</code>对，其中<code>begin</code>是个迭代器，<code>n</code>是元素数量</li>
<li>一个<code>begin,pred</code>对，其中<code>begin</code>是个迭代器，<code>pred</code>是个谓词；
  如果对于迭代器<code>p</code>来说，<code>pred(p)</code>为<code>true</code>，
  我们就到达了序列的末尾。
  这给了我们数不清的序列，并且序列可以“随时按需（on the fly）”生成。</li>
</ul>
<p><code>Range</code>这个概束让我们可以用<code>sort(v)</code>取代<code>sort(v.begin(),v.end())</code>，
后者是STL自1994年开始的使用方式。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">template</span>&lt;BoundedRange R&gt;
    <span class="hljs-keyword">requires</span> Sortable&lt;R&gt;
<span class="hljs-type">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(R&amp; r)</span>
</span>{
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">sort</span>(<span class="hljs-built_in">begin</span>(r),<span class="hljs-built_in">end</span>(r));
}
</code></pre>
<p><code>Sortable</code>的关系默认是<code>less</code>。</p>
<p>一般来说，在标准库算法要求用一对迭代器表示某个序列的地方，
C++20就允许使用一个<code>Range</code>作为简化的替代写法。</p>
<p><a class="en-page-number" id="158"></a></p>
<p>除<code>Range</code>之外，C++20还提供许多便利的概束。
这些概束定义在头文件<code>&lt;ranges&gt;</code>、<code>&lt;iterator&gt;</code>和<code>concepts</code>中。</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>核心语言概束&lt;concepts&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Same&lt;T,U&gt;</code></td>
            <td><code>T</code>和<code>U</code>是相同的类型</td>
        </tr>
        <tr>
            <td><code>DerivedFrom&lt;T,U&gt;</code></td>
            <td><code>T</code>继承自<code>U</code></td>
        </tr>
        <tr>
            <td><code>ConvertibleTo&lt;T,U&gt;</code></td>
            <td>一个<code>T</code>可以转化成一个<code>U</code></td>
        </tr>
        <tr>
            <td><code>CommonReference&lt;T,U&gt;</code></td>
            <td><code>T</code>和<code>U</code>的共通引用类型相同</td>
        </tr>
        <tr>
            <td><code>Common&lt;T,U&gt;</code></td>
            <td><code>T</code>和<code>U</code>的共通类型相同</td>
        </tr>
        <tr>
            <td><code>Integral&lt;T&gt;</code></td>
            <td><code>T</code>是个整数类型</td>
        </tr>
        <tr>
            <td><code>SignedIntegral&lt;T&gt;</code></td>
            <td><code>T</code>是个有符号整数类型</td>
        </tr>
        <tr>
            <td><code>UnsignedIntegral&lt;T&gt;</code></td>
            <td><code>T</code>是个无符号整数类型</td>
        </tr>
        <tr>
            <td><code>Assignable&lt;T,U&gt;</code></td>
            <td><code>U</code>可以赋值给<code>T</code></td>
        </tr>
        <tr>
            <td><code>SwappableWith&lt;T,U&gt;</code></td>
            <td><code>T</code>和<code>U</code>可以被<code>std:swap()</code></td>
        </tr>
        <tr>
            <td><code>Swappable&lt;T&gt;</code></td>
            <td>SwappableWith&lt;T,T&gt;</td>
        </tr>
    </tbody>
</table>

<p>对于某些算法，需要在应用于多个相关类型的时候具备数学上的合理性，
<code>Common</code>在定义这些算法的时候就很重要。
<code>Common&lt;T,U&gt;</code>是指某个类型<code>C</code>，可以把<code>T</code>和<code>U</code>都先转换成<code>C</code>进行比对。
例如，当我们可能想要把<code>std::string</code>跟C-风格字符串（<code>char*</code>），
或者把<code>int</code>跟<code>double</code>进行比对，但不会把<code>std::string</code>和<code>int</code>进行比对。
在用于定义<code>Common</code>时，为确定<code>common_type_t</code>的特化，适宜的方式为：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">using</span> <span class="hljs-type">common_type_t</span>&lt;std::string,<span class="hljs-type">char</span>*&gt; = std::string;
<span class="hljs-keyword">using</span> <span class="hljs-type">common_type_t</span>&lt;<span class="hljs-type">double</span>,<span class="hljs-type">int</span>&gt; = <span class="hljs-type">double</span>;
</code></pre>
<p><code>Common</code>的定义略有点棘手，但解决了一个很难的基本问题。
幸运的是，除非需要进行操作的混合类型在库中（尚）无适当的定义，
我们无需为<code>common_type_t</code>定义一个特化。
在定义那些需要对不同的类型做比对的概束和算法时，
多数都用到了<code>Common</code>或<code>CommonReference</code>。</p>
<p>与比对相关的概束受到了来自 [Stepanov,2009] 的重要影响：</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>比对相关的概束&lt;concepts&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Boolean&lt;T&gt;</code></td>
            <td><code>T</code>可用作布尔类型（Boolean）</td>
        </tr>
        <tr>
            <td><code>WeaklyEqualityComparableWith&lt;T,U&gt;</code></td>
            <td><code>T</code>与<code>U</code>可使用<code>==</code>和<code>!=</code>进行相等性比对</td>
        </tr>
        <tr>
            <td><code>WeaklyEqualityComparable&lt;T&gt;</code></td>
            <td><code>WeaklyEqualityComparableWith&lt;T,T&gt;</code></td>
        </tr>
        <tr>
            <td><code>EqualityComparableWith&lt;T,U&gt;</code></td>
            <td><code>T</code>和<code>U</code>可使用<code>==</code>做等价性比对</td>
        </tr>
        <tr>
            <td><code>EqualityComparable&lt;T&gt;</code></td>
            <td><code>EqualityComparableWith&lt;T,T&gt;</code></td>
        </tr>
        <tr>
            <td><code>StrictTotallyOrderedWith&lt;T,U&gt;</code></td>
            <td>
                <code>T</code>和<code>U</code>可使用
                <code>&lt;</code>、<code>&lt;=</code>、
                <code>&gt;</code>和<code>&gt;=</code>
                进行比对，得出全序关系
            </td>
        </tr>
        <tr>
            <td><code>StrictTotallyOrdered&lt;T&gt;</code></td>
            <td><code>StrictTotallyOrderedWith&lt;T,T&gt;</code></td>
        </tr>
    </tbody>
</table>

<p><code>WeaklyEqualityComparableWith</code>和<code>WeaklyEqualityComparable</code>二者的使用，
揭示了（到目前为止一直都）被忽视的重载机会。</p>
<p><a class="en-page-number" id="159"></a></p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>对象概束&lt;concepts&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Destructible&lt;T&gt;</code></td>
            <td><code>T</code>可被销毁且可用一元的<code>&amp;</code>获取其地址</td>
        </tr>
        <tr>
            <td><code>Constructible&lt;T,Args&gt;</code></td>
            <td><code>T</code>可通过一个<code>Args</code>类型的参数列表构造</td>
        </tr>
        <tr>
            <td><code>DefaultConstructible&lt;T&gt;</code></td>
            <td><code>T</code>有默认构造函数</td>
        </tr>
        <tr>
            <td><code>MoveConstructible&lt;T&gt;</code></td>
            <td><code>T</code>有转移构造函数</td>
        </tr>
        <tr>
            <td><code>CopyConstructible&lt;T&gt;</code></td>
            <td><code>T</code>有拷贝构造函数和转移构造函数</td>
        </tr>
        <tr>
            <td><code>Movable&lt;T&gt;</code></td>
            <td>
                <code>MoveConstructible&lt;T&gt;</code>、
                <code>Assignable&lt;T&amp;,T&gt;</code>和
                <code>Swapable&lt;T&gt;</code>
            </td>
        </tr>
        <tr>
            <td><code>Copyable&lt;T&gt;</code></td>
            <td>
                <code>CopyConstructable&lt;T&gt;</code>、
                <code>Movable&lt;T&gt;</code>和
                <code>Assignable&lt;T,const T&amp;&gt;</code>
            </td>
        </tr><tr>
            <td><code>Semiregular&lt;T&gt;</code></td>
            <td>
                <code>Copyable&lt;T&gt;</code>和
                <code>DefaultConstructable&lt;T&gt;</code>
            </td>
        </tr><tr>
            <td><code>Regular&lt;T&gt;</code></td>
            <td>
                <code>SemiRegular&lt;T&gt;</code>和
                <code>EqualityComparable&lt;T&gt;</code>
            </td>
        </tr>
    </tbody>
</table>

<p><code>Regular</code>是类型的理想状态。
<code>Regular</code>类型用起来大体和<code>int</code>差不多，
并且在某个类型的具体应用（§7.2）方面省却了许多操心。
类中默认<code>==</code>的缺失，意味着多数类只能以<code>SemiRegular</code>的形式面世，
尽管它们中的多数都本可以并应该成为<code>Regular</code>。</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>可调用概束&lt;concepts&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Invocable&lt;F,Args&gt;</code></td>
            <td><code>F</code>可通过一个<code>Args</code>类型的参数列表调用</td>
        </tr>
        <tr>
            <td><code>InvocableRegular&lt;F,Args&gt;</code></td>
            <td>
                <code>F</code>可通过一个<code>Args</code>类型的参数列表调用，并
                <a href="https://en.cppreference.com/w/cpp/concepts/invocable#Equality_preservation" title="std::regular_invocable" target="_blank"><strong>维持等同性</strong></a>
            </td>
        </tr>
        <tr>
            <td><code>Predicate&lt;F,Args&gt;</code></td>
            <td><code>F</code>可通过一个<code>Args</code>类型的参数列表调用，返回bool值</td>
        </tr>
        <tr>
            <td><code>Relation&lt;F,T,U&gt;</code></td>
            <td><code>Predicate&lt;F,T,U&gt;</code></td>
        </tr>
        <tr>
            <td><code>StrictWeakOrder&lt;F,T,U&gt;</code></td>
            <td>
                可确保
                <a href="https://en.cppreference.com/w/cpp/concepts/strict_weak_order" title="std::strict_weak_order" target="_blank"><strong>严格弱序</strong></a>
                的<code>Relation&lt;F,T,U&gt;</code>
            </td>
        </tr>
    </tbody>
</table>

<p>对于某个函数<code>f()</code>，如果<code>x==y</code>可导致<code>f(x)==f(y)</code>，
则该函数是<em>维持等同性（equality preserving）</em>的。</p>
<p>严格弱序（strict weak ordering）是标准库针对顺序比对通常的假设，比如<code>&lt;</code>；
如果你觉得有必要了解就查一下（或者点击表格中该名称的链接——译者）。</p>
<p><code>Relation</code>和<code>StrictWeakOrder</code>仅在语意上有所差别。
我们（目前）还无法在代码层面表示这一差异，因此这两个命名仅体现了我们的意图。</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>迭代器概束&lt;iterators&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Iterator&lt;I&gt;</code></td>
            <td><code>I</code>可被<code>++</code>自增或<code>*</code>解引用</td>
        </tr>
        <tr>
            <td><code>Sentinel&lt;S,I&gt;</code></td>
            <td>
                <code>S</code>是某个<code>Iterator</code>类型的哨兵，
                就是说，<a href="https://en.cppreference.com/w/cpp/iterator/sentinel_for" title="此处较费解，请参阅 std::sentinel_for" target="_blank"><code>S</code>是个用于<code>I</code>的值类型的谓词</a>
            </td>
        </tr>
        <tr>
            <td><code>SizedSentinel&lt;S,I&gt;</code></td>
            <td><code>S</code>是个哨兵，且可以用<code>-</code>运算符和<code>I</code>运算（即减法运算<code>s-i</code>——译者）</td>
        </tr>
        <tr>
            <td><code>InputIterator&lt;I&gt;</code></td>
            <td><code>I</code>是个输入迭代器，<code>*</code>可用于只读操作</td>
        </tr>
        <tr>
            <td><code>OutputIterator&lt;I&gt;</code></td>
            <td><code>I</code>是个输出迭代器，<code>*</code>可用于只写操作</td>
        </tr>
        <tr>
            <td><code>ForwardIterator&lt;I&gt;</code></td>
            <td>
                <code>I</code>是个前向迭代器，支持
                <a href="https://en.cppreference.com/w/cpp/iterator/forward_iterator#Semantic_requirements" title="此术语详情请参阅 std::forward_iterator" target="_blank"><strong>multi-pass</strong></a>
            </td>
        </tr>
        <tr>
            <td><code>BidirectionalIterator&lt;I&gt;</code></td>
            <td>
                <code>I</code>是个<code>ForwardIterator</code>，支持<code>--</code>
            </td>
        </tr>
        <tr>
            <td><code>RandomAccessIterator&lt;I&gt;</code></td>
            <td>
                <code>I</code>是个<code>BidirectionalIterator</code>，
                支持<code>+</code>、<code>-</code>、<code>+=</code>、<code>-=</code>和<code>[]</code>
            </td>
        </tr>
        <tr>
            <td><code>Permutable&lt;I&gt;</code></td>
            <td>
                <code>I</code>是个<code>ForwardIterator</code>，
                并且<code>I</code>支持移动和交换元素
            </td>
        </tr>
        <tr>
            <td><code>Mergeable&lt;I1,I2,R,O&gt;</code></td>
            <td>
                可以按<code>Relation&lt;R&gt;</code>把有序序列<code>I2</code>和<code>I2</code>合并入<code>O</code>
            </td>
        </tr>
        <tr>
            <td><code>Sortable&lt;I&gt;</code></td>
            <td>
                可以按<code>less</code>把承载<code>I</code>的序列进行排序
            </td>
        </tr>
        <tr>
            <td><code>Sortable&lt;I,R&gt;</code></td>
            <td>
                可以按<code>Relation&lt;R&gt;</code>把承载<code>I</code>的序列进行排序
            </td>
        </tr>
    </tbody>
</table>

<p><a class="en-page-number" id="160"></a></p>
<p>对于给定的算法，迭代器的不同类型（分类）可用于选择最优的方式；
见 §7.2.2 和 §13.9.1。对于<code>InputIterator</code>的范例，请参见 §12.4。</p>
<p>哨兵的基本思路是这样的：我们针对某个区间进行迭代，
该区间始自一个迭代器，直到谓词对于某个元素为 true 终止。
这样，一个迭代器<code>p</code>和一个哨兵<code>s</code>就定义了一个区间<code>[p:s(*p)]</code>。
例如，为了遍历以指针作为迭代器的C-风格字符串，
可以为其哨兵定义一个谓词：</p>
<pre><code class="lang-cpp">[](<span class="hljs-type">const</span> <span class="hljs-type">char</span>* p) {<span class="hljs-keyword">return</span> *p==<span class="hljs-number">0</span>; }
</code></pre>
<p>与C++20中的定义相比，此处<code>Mergeable</code>和<code>Sortable</code>的介绍进行了简化。</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>区间概束&lt;ranges&gt;</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>Range&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，由一个起始迭代器和一个哨兵界定</td>
        </tr>
        <tr>
            <td><code>SizedRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其size可在常数时间内获知</td>
        </tr>
         <tr>
            <td><code>View&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其复制、移动和赋值的执行是常数时间</td>
        </tr>
        <tr>
            <td><code>BoundedRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器和哨兵的类型一致</td>
        </tr>
        <tr>
            <td><code>InputRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器类型符合 InputIterator 的要求</td>
        </tr>
        <tr>
            <td><code>OutputRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器类型符合 OutputIterator 的要求</td>
        </tr>
        <tr>
            <td><code>ForwardRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器类型符合 ForwardIterator 的要求</td>
        </tr>
        <tr>
            <td><code>BidirectionalRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器类型符合 BidirectionalIterator 的要求</td>
        </tr>
        <tr>
            <td><code>RandomAccessRange&lt;R&gt;</code></td>
            <td><code>R</code>是个区间，其迭代器类型符合 RandomAccessIterator 的要求</td>
        </tr>
    </tbody>
</table>

<p><code>&lt;ranges&gt;</code>里还有几个其它的概束，但此表也够入门的了。</p>
<h2 id="12.8">12.8 容器算法 </h2>
<p>在等不及 Range 概束的情况下，可以定义我们自己的简化版区间算法。
例如，提供<code>sort(v)</code>这种简短写法取代<code>sort(v.begin(),v.end())</code>可谓易如反掌：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">namespace</span> Estd {
    <span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> std;

    <span class="hljs-function"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> C&gt;
    <span class="hljs-type">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(C&amp; c)</span>
    </span>{
        <span class="hljs-built_in">sort</span>(c.<span class="hljs-built_in">begin</span>(),c.<span class="hljs-built_in">end</span>());
    }

    <span class="hljs-function"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> C, <span class="hljs-keyword">typename</span> Pred&gt;
    <span class="hljs-type">void</span> <span class="hljs-title">sort</span><span class="hljs-params">(C&amp; c, Pred p)</span>
    </span>{
        <span class="hljs-built_in">sort</span>(c.<span class="hljs-built_in">begin</span>(),c.<span class="hljs-built_in">end</span>(),p);
    }

    <span class="hljs-comment">// ...</span>
}
</code></pre>
<p>我把容器版本的<code>sort()</code>（和其它算法）置于独有的命名空间<code>Estd</code></p>
<p><a class="en-page-number" id="161"></a></p>
<p>（“extended <code>std</code>”）中，以免跟其他程序员对命名空间<code>std</code>的使用产生冲突，
同时还便于将来用<code>Range</code>版本取代这个权宜之计。</p>
<h2 id="12.9">12.9 并行算法 </h2>
<p>当对大量数据项执行同样的操作时，只要针对不同数据项的运算相互独立，
就能够以并行的方式去执行：</p>
<ul>
<li><em>并行执行（parallel execution）</em>：
  任务在多个线程上执行（通常运行在多个处理器核心上）</li>
<li><em>向量化执行（vectorized execution）</em>：
  任务在单一线程上以向量化（vectorization）方式执行，
  也称作<em>SIMD（“Single Instruction, Multiple Data”）</em>。</li>
</ul>
<p>标准库对这两种都提供支持，还可以指定顺序执行，在<code>&lt;execution&gt;</code>中有：</p>
<ul>
<li><code>seq</code>：顺序执行</li>
<li><code>par</code>：（在可行的情况下）并行执行</li>
<li><code>par_unseq</code>：（在可行的情况下）并行执行 和/或 非顺序（向量化）执行。</li>
</ul>
<p>以<code>std::sort()</code>为例：</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">sort</span>(v.<span class="hljs-built_in">begin</span>(),v.<span class="hljs-built_in">end</span>());            <span class="hljs-comment">// 顺序执行</span>
<span class="hljs-built_in">sort</span>(seq,v.<span class="hljs-built_in">begin</span>(),v.<span class="hljs-built_in">end</span>());        <span class="hljs-comment">// 顺序执行（与默认方式相同）</span>
<span class="hljs-built_in">sort</span>(par,v.<span class="hljs-built_in">begin</span>(),v.<span class="hljs-built_in">end</span>());        <span class="hljs-comment">// 并行执行</span>
<span class="hljs-built_in">sort</span>(par_unseq,v.<span class="hljs-built_in">begin</span>(),v.<span class="hljs-built_in">end</span>());  <span class="hljs-comment">// 并行执行 和/或 向量化执行</span>
</code></pre>
<p>至于并行执行 和/或 向量化执行是否划算，要取决于算法、序列中元素的数量、硬件，
以及运行该程序的机器的利用率等等。
因此<em>执行策略标志（execution policy indicators）</em>仅仅是个示意（hint）。
编译器 和/或 运行时调度器将决定在多大程度上采用并发。
这并非无关紧要的小事，此外，“切勿未经测试就对性能下断言”的规则在此处尤为重要。</p>
<p>绝大多数标准库算法，包括 §12.6 表中除<code>equal_range</code>外的全部，
都能像<code>sort()</code>使用<code>par</code>和<code>par_unseq</code>那样被并行化和向量化。
为什么<code>equal_range()</code>不行呢？因为到目前为止，它尚无有益的并行算法。</p>
<p>很多并行算法主要用于数值数据；参见 §14.3.1。</p>
<p>采用并行执行时，请确保避免数据竞争（§15.2）和死锁（§15.5）。</p>
<h2 id="12.10">12.10 忠告 </h2>
<ul>
<li>[1] STL 算法可操作一个或多个序列；§12.1。</li>
<li>[2] 输入序列是由一对迭代器定义的半开区间；§12.1。</li>
<li>[3] 在进行查找时，算法通常返回输入序列的结尾以表示“未找到”；§12.2。</li>
<li>[4] 算法不会直接在其参数序列中增添或删减元素；§12.2，§12.6。</li>
<li>[5] 写循环时，考虑一下能否以一个通用算法实现；§12.2。</li>
</ul>
<p><a class="en-page-number" id="162"></a></p>
<ul>
<li>[6] 请使用谓词和其它函数对象为标准算法赋予更广泛的意义；§12.5，§12.6。</li>
<li>[7] 谓词绝不可修改其参数；§12.5。</li>
<li>[8] 请通晓标准库算法，并用其代替手写的循环；§12.6。</li>
<li>[9] 在 迭代器对 的风格显得冗长时，可以引入一个 容器/区间 版本的算法；§12.8。</li>
</ul>
<blockquote id="fn_1">
<sup>1</sup>. 著名的“奥卡姆剃刀”法则，此处作者可能误会了说这短引言作者的名字，因为其名字应该是“William of Occam”，意思是“奥卡姆这个地方的威廉”，作者的写法里“奥卡姆”是他的姓。该名词有专门的的<a href="https://zh.wikipedia.org/wiki/%E5%A5%A5%E5%8D%A1%E5%A7%86%E5%89%83%E5%88%80" target="_blank">维基百科页面</a> —— 译者注<a href="#reffn_1" title="Jump back to footnote [1] in the text."> ↩</a>
</blockquote>

<script>console.log(window.location.pathname)</script>
<div id="disqus_thread"></div>
<script>

/**
*  RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
*  LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/
/*
var disqus_config = function () {
this.page.url = window.location.href;
this.page.identifier = window.location.pathname;
};
*/
(function() { // DON'T EDIT BELOW THIS LINE
var d = document, s = d.createElement('script');
s.src = 'https://a-tour-of-cpp-2nd-cn.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript" target="_blank">comments powered by Disqus.</a></noscript>
                                
    

                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="ch11.html" class="navigation navigation-prev " aria-label="Previous page: 11 容器">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="ch13.html" class="navigation navigation-next " aria-label="Next page: 13 实用功能">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"ch":12,"title":"12 算法","level":"1.14","depth":1,"next":{"title":"13 实用功能","level":"1.15","depth":1,"path":"ch13.md","ref":"ch13.md","articles":[]},"previous":{"title":"11 容器","level":"1.13","depth":1,"path":"ch11.md","ref":"ch11.md","articles":[]},"dir":"ltr"},"config":{"plugins":["@dogatana/page-toc-button","@dogatana/back-to-top-button","copy-code-button","forkmegithub","disqus-legacy"],"root":"./src","styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"pluginsConfig":{"@dogatana/back-to-top-button":{},"styles":{"website":"styles/website.css"},"search":{},"@dogatana/page-toc-button":{},"lunr":{"maxIndexSize":1000000,"ignoreSpecialCharacters":false},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"disqus-legacy":{"shortname":"a-tour-of-cpp-2nd-cn"},"copy-code-button":{},"forkmegithub":{"color":"orange","url":"https://github.com/windsting/a-tour-of-cpp-2nd-cn"},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false}},"theme":"default","author":"Windsting","pdf":{"pageNumbers":true,"fontSize":14,"fontFamily":"Arial","paperSize":"a5","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56},"embedFonts":false},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"C++导览 第二版 简体中文版","language":"zh-hans","links":{"sidebar":{"Github Link":"https://github.com/windsting/a-tour-of-cpp-2nd-cn"}},"gitbook":"*","description":"A Tour of C++ (第二版) 非官方中译本"},"file":{"path":"ch12.md","mtime":"2023-02-11T10:19:36.097Z","type":"markdown"},"gitbook":{"version":"5.1.1","time":"2023-10-27T09:54:29.738Z"},"basePath":".","book":{"language":""}});
        });
    </script>
</div>

        
    <noscript>
        <style>
            .honkit-cloak {
                display: block !important;
            }
        </style>
    </noscript>
    <script>
        // Restore sidebar state as critical path for prevent layout shift
        function __init__getSidebarState(defaultValue){
            var baseKey = "";
            var key = baseKey + ":sidebar";
            try {
                var value = localStorage[key];
                if (value === undefined) {
                    return defaultValue;
                }
                var parsed = JSON.parse(value);
                return parsed == null ? defaultValue : parsed;
            } catch (e) {
                return defaultValue;
            }
        }
        function __init__restoreLastSidebarState() {
            var isMobile = window.matchMedia("(max-width: 600px)").matches;
            if (isMobile) {
                // Init last state if not mobile
                return;
            }
            var sidebarState = __init__getSidebarState(true);
            var book = document.querySelector(".book");
            // Show sidebar if it enabled
            if (sidebarState && book) {
                book.classList.add("without-animation", "with-summary");
            }
        }

        try {
            __init__restoreLastSidebarState();
        } finally {
            var book = document.querySelector(".book");
            book.classList.remove("honkit-cloak");
        }
    </script>
    <script src="gitbook/gitbook.js"></script>
    <script src="gitbook/theme.js"></script>
    
        
        <script src="gitbook/@dogatana/honkit-plugin-page-toc-button/plugin.js"></script>
        
    
        
        <script src="gitbook/@dogatana/honkit-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-forkmegithub/plugin.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-search/search-engine.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-search/search.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-lunr/lunr.min.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-lunr/search-lunr.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

